package org.basis.algorithm.practice;

import java.util.Stack;

/**
 * 用栈来实现队列
 *
 * @author Mr_wenpan@163.com 2022/03/21 18:06
 */
public class StackImplementQueue {

    public static void main(String[] args) {
        MyQueue<String> myQueue = new MyQueue<>();
        myQueue.addLast("wenpan");
        myQueue.addLast("hello");
        myQueue.addLast("world");
        myQueue.addLast("1");
        myQueue.addLast("2");
        myQueue.addLast("3");
        for (int i = 0; i < 5; i++) {
            String str = myQueue.pollFirst();
            System.out.println(str);
        }
        myQueue.addLast("4");
        myQueue.addLast("5");
        while (!myQueue.isEmpty()) {
            String str = myQueue.pollFirst();
            System.out.println(str);
        }
    }
}

/**
 * 使用两个栈来实现队列
 */
class MyQueue<T> {

    private Stack<T> stack1;
    private Stack<T> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /**
     * 入队列
     */
    public void addLast(T val) {
        // 先将stack1的数据全部转移到stack2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        // 将val压入stack2栈顶
        stack2.push(val);
    }

    /**
     * 出队列
     */
    public T pollFirst() {
        while (!stack2.isEmpty()) {
            // 将第二个栈里的数据从栈顶开始弹出，然后装入到stack1中
            stack1.push(stack2.pop());
        }
        return stack1.pop();
    }

    /**
     * 获取队列头元素
     */
    public T peekFirst() {
        while (!stack2.isEmpty()) {
            // 将第二个栈里的数据从栈顶开始弹出，然后装入到stack1中
            stack1.push(stack2.pop());
        }
        return stack1.peek();
    }

    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

}
